import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-08-26
 * Time: 17:39
 */
public class TreeHeap {
    int[] elem;
    int usedsize;//记录了当前堆的元素个数和可以存放元素的下标位置
    public TreeHeap(){
        this.elem = new int[10];
    }
    public void inital(int[] array){
        elem = Arrays.copyOf(array,array.length);
        usedsize = elem.length;
    }
    public void create(){
        for (int i = (usedsize-1-1)/2; i >=0 ; i--) {//从最后一颗子树开始
            shiftdwom(i,usedsize);

        }

    }
    private  void  shiftdwom(int parent,int len){
        //创建左子树节点
        int child = 2*parent+1;
        //能够比较大小的前提是必须促存在左子树节点
        while (child < len){//向下传递,循环比较
            //比较左右子树节点的大小
            //比较的前提是必须存在右子树节点
            if(child+1<len && elem[child] < elem[child+1]){
                child++;//child记录了根节点的最大值
            }
            if (elem[parent] <elem[child]){
                swap(elem,parent,child);
                //如果交换完了之后,子树又不是大堆了,继续循环,向下传递
                parent = child;
                child = 2*parent+1;
            }else{//如果elem[parent] >= elem[child]),则不用在往下传递了,因为本来就是从最后一颗子树创建,走到这里,当前根的左右子树的堆都已经创建过了
                break;
            }
        }

    }
    private  void  swap(int[] elem,int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    /**
     * 增加:保证也是大堆
     */
    private boolean isFull(){
        return usedsize == elem.length;
    }
    public  void  offer(int x){
        //判满
        if(isFull()){
        elem = Arrays.copyOf(elem,elem.length*2);
        }
        //新增了一个元素
        elem[usedsize] = x;
        usedsize++;
        shiftUp(usedsize-1);//下标从0开始
    }

    /**
     * shiftUp 向上调整
     * @param len
     */
    public void shiftUp(int len){
        //child == usedsize 处存放要插入的元素
        int child = len;
        int parent = (child-1)/2;
        while (child > 0){
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                //如果还不为大堆,继续往上传递
                child = parent;
                parent = (child-1)/2;
            }else {//在插入之前已经为大根堆,因此不用再继续调整
                break;
            }
        }
    }
    /**
     * 删除:只能删除堆顶元素
     * 堆顶元素与最后一个元素交换
     * usedsize--
     * 堆顶元素再进行向下调整
     */
    public int poll(){
        //空堆
        if(isEmpty()){
            return -1;
        }
        int ret = elem[0];
        swap(elem,0,usedsize-1);
        usedsize--;
        shiftdwom(0,usedsize);
        return ret;
    }
    public boolean isEmpty(){
        return usedsize==0;
    }
    /**
     * 堆排序:在大根堆的情况下
     */
    public void heapSort(){//usedsize == 10
        int end = usedsize - 1;//end == 9
        usedsize--;//usedsize == 9
        while (end>0){
            swap(elem,0,end);//只用调整九个元素了,所以结束条件==end==9
            shiftdwom(0,end);
            //向下调整完了之后,end再--
            end--;
        }

    }
}
